#pragma once
#include "DemoSort.hpp"
#include "Sort.hpp"
#include "Search.hpp"

std::vector<std::string> words;
void LoadEnglishWords()
{
	std::string words_path = std::string(__FILE__) + "\\..\\words_alpha.txt";
	FILE* file_handle = nullptr;
	fopen_s(&file_handle, words_path.c_str(), "r+");
	if (!file_handle)
	{
		std::cout << "english words file open failed.." << std::endl;
		return;
	}
	char buffer[124] = { 0 };
	while (fgets(buffer, 124, file_handle))
	{
		words.push_back(buffer);
		words.back().erase(words.back().find_last_not_of('\n') + 1);
	}

	std::cout << "words size:" << words.size() << std::endl;
	fclose(file_handle);
}

void TestBinarySearch()
{
	//quick sort words time costed:6185
	//binary search time costed : 25978
	clock_t begin = clock();
	QuickSort(words.data(), words.size());
	clock_t end = clock();
	std::cout << "quick sort words time costed:" << end - begin << std::endl;

	std::vector<std::string> search_words;
	GenerateTestData(search_words, 1000000);
	for (int i = 0; i < 1000000; ++i)
		search_words.push_back(words[rand() % words.size()]);

	begin = clock();
	for (auto& word : search_words)
		BinarySearch(words.data(), words.size(), word);
	end = clock();

	std::cout << "time costed:" << end - begin << std::endl;
}

void TestHashSearch()
{
	/*
	  words size:370103
	  construct hash table time cost:1527
	  
	  bin size:0 bin count:258928
	  bin size:1 bin count:182380
	  bin size:2 bin count:64778
	  bin size:3 bin count:15104
	  bin size:4 bin count:2696
	  bin size:5 bin count:356
	  bin size:6 bin count:39
	  bin size:7 bin count:7
	  bin size:8 bin count:1
	  
	  time costed:3830
	*/
	HashTable<std::string*> hash_table(
		[](std::string* const& val, int bins_size)->int
	{
		/*static std::map<const std::string*, int> calced_hashes;
		if (calced_hashes.count(&val) > 0)
			return calced_hashes[&val] % bins_size;*/

		int hash = 0;
		for (size_t i = 0; i < (*val).size(); ++i)
			hash = 31 * hash + (*val)[i];
		if (hash < 0)
			hash = -hash;
		//calced_hashes[&val] = hash;

		return hash % bins_size;
	});

	clock_t begin = clock();
	for (auto& each : words)
		hash_table.Add(&each);
	clock_t end = clock();
	std::cout << "construct hash table time cost:" << end - begin << std::endl;

	hash_table.PrintHashDistribution();

	std::vector<std::string> search_words;
	GenerateTestData(search_words, 1000000);
	for (int i = 0; i < 1000000; ++i)
		search_words.push_back(words[rand() % words.size()]);

	begin = clock();
	for (auto& word : search_words)
		hash_table.IsExist(&word);
	end = clock();
	std::cout << "time costed:" << end - begin << std::endl;
}

void TestHashDistribution()
{
	HashTable<std::string*> hash_table(
		[](std::string* const & val, int bins_size)->int
	{
		unsigned long long hash = 0;
		for (size_t i = 0; i < (*val).size(); ++i)
			hash = (hash* 100663319 + (*val)[i])% 201326611;

		return hash % bins_size;
	});

	clock_t begin = clock();
	for (auto& each : words)
		hash_table.Add(&each);
	clock_t end = clock();
	std::cout << "construct hash table time cost:" << end - begin << std::endl;

	hash_table.PrintHashDistribution();
}

void TestBinarySearchTree()
{
	std::vector<int> test_datas;
	GenerateTestData(test_datas, 1500000);

	BinarySearchTree<int> bst;

	clock_t begin = clock();
	int tree_size = 0;
	for (auto& each : test_datas)
		bst.Add(each);
	clock_t end = clock();
	std::cout << "bst construct time costed:" << end - begin << std::endl;

	//std::vector<int> searchs;
	//GenerateTestData(searchs, 1000000);
	//for (int i = 0; i < 1000000; ++i)
	//	searchs.push_back(test_datas[rand() % test_datas.size()]);
	//std::cout << "test search data generate finished..." << std::endl;

	begin = clock();
	std::vector<int> removes;
	GenerateTestData(removes, 500000);
	for (int i = 0; i < 500000; ++i)
		removes.push_back(test_datas[rand() % test_datas.size()]);
	for (auto& each : removes)
		bst.Remove(each);
	end = clock();
	std::cout << "bst remove time cost:" << end - begin << std::endl;


	//begin = clock();
	//for (auto& each : searchs)
	//	bst.IsExist(each);
	//end = clock();
	//std::cout << "bst search time costed:" << end - begin << std::endl;
}

void RunSearchDemo()
{
	//LoadEnglishWords();

	//TestBinarySearch();
	//TestHashSearch();
	//TestHashDistribution();
	TestBinarySearchTree();
	return;
}